/*
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：
    首先找到需要删除的节点；
    如果找到了，删除它。

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。


一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7


*/

//递归
/*
如果目标节点没有子节点，我们可以直接移除该目标节点。
如果目标节只有一个子节点，我们可以用其子节点作为替换。
如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点


*/
class Solution
{
public:
    TreeNode *deleteNode(TreeNode *root, int key)
    {
        if (!root)
            return NULL;
        if (key < root->val)
        {
            // 找到key所在的位置
            root->left = deleteNode(root->left, key);
            return root;
        }
        if (key > root->val)
        {
            // 找到key所在的位置
            root->right = deleteNode(root->right, key);
            return root;
        }
        // 当key == root -> val， 即找到目标点时
        //当目标点只有一边子树时
        if (!root->left)
        {
            // 若没有左子树，删除目标点，右子树接上
            TreeNode *temp = root->right;
            delete (root);
            return temp;
        }
        if (!root->right)
        {
            // 若没有右子树，删除目标点，左子树接上
            TreeNode *temp = root->left;
            delete (root);
            return temp;
        }
        //当目标点左右都有子树时
        TreeNode *temp = root->right; // 找到右子树中最小的值，即进入右子树后一直向左遍历
        while (temp->left)
            temp = temp->left;
        swap(root->val, temp->val);                 // 交换值
        root->right = deleteNode(root->right, key); // 进入遍历，删除key
        return root;
    }
};

//迭代
class Solution
{
public:
    int sonName = 0; // 左定义为0，右定义为1
    TreeNode *deleteNode(TreeNode *root, int key)
    {
        // 特殊处理根结点
        if (root == NULL || (root->val == key && root->left == NULL && root->right == NULL))
            return NULL;
        // ans是一个指向结构指针数组的指针
        TreeNode **ans = findAncestor(root, key);
        TreeNode *ancestor = *ans;
        TreeNode *toDelete = *(ans + 1);
        // 仅当被删除节点不为空进行删除操作
        while (toDelete != NULL)
        {
            // 待删除节点无儿子，说明已经进行到了最后一步，直接删除即可
            if (toDelete->left == NULL && toDelete->right == NULL)
            {
                // 判断删除左儿子或右儿子
                if (sonName == 0)
                    ancestor->left = NULL;
                else
                    ancestor->right = NULL;
                break;
            }
            // 待删除结点右结点存在，找到右节点的最左子树作为后继节点替换
            else if (toDelete->right != NULL)
            {
                TreeNode *index = toDelete->right;
                ancestor = toDelete;
                sonName = 1;
                while (index->left != NULL)
                {
                    ancestor = index;
                    sonName = 0;
                    index = index->left;
                }
                // 交换节点值并移动删除标记
                swap(index->val, toDelete->val);
                toDelete = index;
            }
            // 待删除结点仅有左节点或有左右结点，则找到左节点的最右子树作为前驱节点交换
            else
            {
                TreeNode *index = toDelete->left;
                ancestor = toDelete;
                sonName = 0;
                while (index->right != NULL)
                {
                    ancestor = index;
                    sonName = 1;
                    index = index->right;
                }
                // 交换节点值并移动删除标记
                swap(index->val, toDelete->val);
                toDelete = index;
            }
        }
        return root;
    }
    // 返回待删除结点与其祖先结点组成的数组的指针
    TreeNode **findAncestor(TreeNode *root, int key)
    {
        static TreeNode *ans[2] = {NULL, NULL};
        TreeNode *ancestor = root;
        // 特殊处理根结点
        if (root->val == key)
        {
            ans[1] = root;
            return ans;
        }
        // 寻找到答案或者找到头就直接返回结束
        while (true)
        {
            // 相等情况已经在上一轮循环中检查过，只存在大于或小于情况
            if (key < ancestor->val)
            {
                if (ancestor->left == NULL)
                    return ans;
                if (key == ancestor->left->val)
                {
                    ans[0] = ancestor;
                    ans[1] = ancestor->left;
                    sonName = 0;
                    return ans;
                }
                else
                    ancestor = ancestor->left;
            }
            else
            {
                if (ancestor->right == NULL)
                    return ans;
                if (key == ancestor->right->val)
                {
                    ans[0] = ancestor;
                    ans[1] = ancestor->right;
                    sonName = 1;
                    return ans;
                }
                else
                    ancestor = ancestor->right;
            }
        }
        return ans;
    }
};
